home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3273 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.6 KB
  1. Path: Rezonet.net!news
  2. From: ray@ultimate-tech.com (Ray Dunn)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 25 Jan 1996 04:56:53 GMT
  6. Organization: Ultimate Technographics Inc.
  7. Message-ID: <4e72il$dvl@ns.RezoNet.NET>
  8. References: <4e61iu$p6e@villa.fc.net>
  9. NNTP-Posting-Host: 204.19.230.7
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=US-ASCII
  12. X-Newsreader: WinVN 0.99.7
  13.  
  14. In referenced article, Avinash Chopde says...
  15. >I am trying to find out what could be the fastest way to compute
  16. >the position of the highest bit in any given integer -- basically, the
  17. >logarithm to the base 2 of any number.
  18.  
  19. I can't think of any way faster than a variation of:
  20.  
  21. /* Returns the Bitnumber of the highest set bit in n.
  22.    Assumes an int is maximum 32-bits long.
  23.    Returns -1 if n == 0
  24.  
  25.    Log2Table is a table filled with the bit-number of the highest bit
  26.    of the numbers 0 through 15
  27. */
  28.  
  29. int FindHighestBitNumber(unsigned int n)
  30. { int i;
  31.   static int Log2Table[16] =
  32.     {-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};
  33.  
  34.   i = 0;
  35.   if (n > 0xFFFF)
  36.   {
  37.     n = (n >> 16) & 0xFFFF;
  38.     i = 16;
  39.   }
  40.   if (n > 0xFF)
  41.   {
  42.     n = n >> 8;
  43.     i += 8;
  44.   }
  45.   if (n > 0xF)
  46.   {
  47.     n = n >> 4;
  48.     i += 4;
  49.   }
  50.   return(Log2Table[n] + i);
  51. }
  52.  
  53. You could also use a union to extract the appropriate byte if speed is 
  54. a concern and shifting is slow on your machine.
  55.  
  56. If you want more speed, then give a 256 entry Log2Table and remove the 
  57. last conditional.
  58. -- 
  59. Ray Dunn (opinions are my own) | Phone: (514) 938 9050
  60. Montreal                       | Phax : (514) 938 5225
  61. ray@ultimate-tech.com          | Home : (514) 630 3749
  62.  
  63.  
  64.